class Solution{
public:
  int countSubstrings(string s){

    int ans = 0;
    // dp[j][i]表示s[i...j]是否是回文串
    bool dp[s.length() + 1][s.length() + 1];
    memset(dp, false, sizeof(dp));
    for(int i = 0; i < s.length(); ++i){
      dp[i][i] = true;
    }

    for(int i = 0; i < s.length(); ++i){
      for(int j = 0; j <= i; ++j){
        if(s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1])){
          dp[j][i] = true;
          ++ans;
        }
      }
    }

    return ans;

  }
};